package main

import "fmt"

type TNode struct {
	val int
	lchild *TNode
	rchild *TNode
}
//递归创建二叉树
//nums数组逐层存放树的结点值，i初始值为0
func createTree(nums []int, i int)*TNode{
	if i > len(nums) || nums[i] == -1{
		return nil
	}
	t := &TNode{val: nums[i]}
	if 2*i+1 < len(nums){
		t.lchild = createTree(nums, 2*i+1)
	}
	if 2*i+2 < len(nums){
		t.rchild = createTree(nums, 2*i+2)
	}
	return t
}
//先序遍历二叉树（根左右）
func (root *TNode)ProTree(){
	if root != nil{
		fmt.Printf("%d, ", root.val)
		root.lchild.ProTree()
		root.rchild.ProTree()
	}
}
//中序遍历（左根右）
func (root *TNode)MidTree(){
	if root != nil{
		root.lchild.MidTree()
		fmt.Printf("%d, ", root.val)
		root.rchild.MidTree()
	}
}
//后序遍历（左右根）
func (root *TNode)OutTree(){
	if root != nil{
		root.lchild.OutTree()
		root.rchild.OutTree()
		fmt.Printf("%d, ", root.val)
	}
}
//层次遍历
func (root *TNode)levelTree(list []*TNode){
	if root != nil{
		list = append(list, root)
		i := 0
		for i < len(list){
			fmt.Printf("%d, ", list[i].val)
			if list[i].lchild != nil{
				list = append(list, list[i].lchild)
			}
			if list[i].rchild != nil{
				list = append(list, list[i].rchild)
			}
			i++
		}
	}
}

func main(){
	nums := []int{1, 2, 3, 4, 5, 6, 7, 8}
	T := createTree(nums, 0)
	list := []*TNode{}
	fmt.Println("层次遍历：")
	T.levelTree(list)
	fmt.Println()
	fmt.Println("先序遍历：")
	T.ProTree()
	fmt.Println()
	fmt.Println("中序遍历：")
	T.MidTree()
	fmt.Println()
	fmt.Println("后序遍历：")
	T.OutTree()
}